package com.yehui.algorithm.dp.backpack;

/**
 * 有 N 件物品和一个容量为 V 的背包。放入第 i 件物品耗费的费用是 C[i]  ,得到的价值是 W[i] 。求解将哪些物品装入背包可使价值总和最大。求出最大总价值。
 *
 * dp[i][j] 标识 i 个物品，j 容量下的最大价值
 *
 * dp[i][j] = max{dp[i-1][j], dp[i-1][V-C[i]] + W[i]}
 *
 * @author 业徽
 * @date 2021/2/9
 */
public class ZeroOneBackpack {

    /**
     * 根据递推公式直接计算
     *
     * @param V
     * @param C
     * @param W
     */
    public int normal(int V, int[] C, int[] W) {
        int[][] dp = new int[C.length + 1][V + 1];
        for (int i = 1; i <= C.length; i++) {
            for (int j = 1; j <= V; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j - C[i - 1] >= 0) {
                    // 总容量j比当前容量 C[i - 1] 大，才能尝试先放 i-1, 然后找 dp[i - 1][j - C[i - 1]]
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - C[i - 1]] + W[i - 1]);
                }
            }
        }

        return dp[C.length][V];
    }

    /**
     * 空间是  n * V 的二维数组
     *
     * 每次只用到了前一行, 可以尝试只用一维数组
     *
     * 先看 dp[i][j] = max{dp[i-1][j], dp[i-1][j-C[i]] + W[i]} 递推公司
     *
     * 容量是从目标 j 开始，往小于 j 的方向找的，
     * 那么我们遍历的时候，先从最终目标 V 开始, 从后往前推导，然后往数组赋值，
     * 这样就不会覆盖递推所需要的前导元素
     *
     *
     * @param V
     * @param C
     * @param W
     * @return
     */
    public int optSpace(int V, int[] C, int[] W) {
        int[] dp = new int[V + 1];
        for (int i = 0; i < C.length; i++) {
            for (int j = V; j >= C[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - C[i]] + W[i]);
            }
        }

        return dp[V];
    }

    /**
     * 当背包的 V 特别大的时候，对于每一个物品都去遍历一遍没有意义，
     * 通过阈值来进行优化，优化的同时可以考虑将数组从大到小排个序：对于 V 很大的情况
     *
     *
     *
     * @param V
     * @param C
     * @param W
     * @return
     */
    public int optLargeV(int V, int[] C, int[] W) {

        int n = C.length;

        int[] dp = new int[V + 1];

        int bound, sum = 0, total = 0;
        for (int i : C) {
            total += i;
        }

        for (int i = 0; i < n; ++i) {
            bound = Math.max(V - total + sum, C[i]);
            sum += C[i];
            for (int j = V; j >= bound; --j) {
                dp[j] = Math.max(dp[j], dp[j - C[i]] + W[i]);
            }
        }

        return dp[V];
    }

}
